def fibonacchi(n: int):
    """
    Simple fimonacchi func. Very slow
    """
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacchi(n-1) + fibonacchi(n-2)



# MEMOIZATION
# Caches values

fibonacchi_cache = {}

def fibonacchi_2(n:int):
    if n in fibonacchi_cache:
        return fibonacchi_cache[n]
    
    if n in (1, 2):
        value = 1
    elif n > 2:
        value = fibonacchi_2(n-1) + fibonacchi_2(n-2)
    else :
        return

    fibonacchi_cache[n] = value
    return value

from functools import lru_cache

@lru_cache(maxsize=1000)
def fibonacchi_3(n: int):
    """
    Simple fibonacchi func. Very slow. But we use cache decorator
    from functools module
    """
    if not isinstance(n, int) or n < 1:
        raise TypeError("n must be a positive int")
    if n in (1, 2):
        return 1
    elif n > 2:
        return fibonacchi_3(n-1) + fibonacchi_3(n-2)

for n in range(1, 1501):
    print(n, ":", fibonacchi_3(n))

#print(fibonacchi_3("11.1"))
